package algorithm.poj.p1000;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.net.URL;
import java.net.URLDecoder;
import java.util.Arrays;

/**
 * 分析：
 * 试图从已有的条件中挖掘可用的信息。
 * 从最后一列，我们可以知道0，1的数目(x个0，y个1)
 * 初次外，我们还知道第一列的前x个都是0，后y个都是1。
 * 从而，我们可以知道0-1有向环中0-0，0-1，1-0，1-1的个数。
 * 
 * 比如，最后一列是1 0 0 1 0的情形一定之这样的：
 * 0 X X X 1
 * 0 X X X 0
 * 0 X X X 0
 * 1 X X X 1
 * 1 X X X 0
 * 所以，初始输入一定是包含3个0，2个1的有向环，并且环中0-0，0-1，1-0，1-1的
 * 个数分别是2，1，1，1。
 * 
 * 这样就可以递归求解。实践证明，这不可取。
 * （字符串长度达到30就会出现内存不够，速度自然很慢。而且出来很多多余的解）
 * 
 * 
 * 
 * 实现：
 * 
 * 经验：
 * 
 * 教训：
 * 
 * 
 * @author wong.tong@gmail.com
 *
 */
public class P1147 {

	public static void main(String[] args) throws Exception {

		InputStream input = null;
		if (false) {
			input = System.in;
		} else {
			URL url = P1147.class.getResource("P1147.txt");
			File file = new File(URLDecoder.decode(url.getPath(), "UTF-8"));
			input = new FileInputStream(file);
		}
		
		BufferedReader stdin = new BufferedReader(new InputStreamReader(input));

//		String line = stdin.readLine();
//		line = stdin.readLine().trim().replaceAll("\\s+", "");
//		
//		String str = f(line);
//		String[] array = nrotate(str);
//		Arrays.sort(array);
//		char[] cs = array[0].toCharArray();
//		
//		for (int i = 0; i < cs.length; i ++) {
//			if (i != 0) {
//				System.out.print(" ");
//			}
//			System.out.print(cs[i]);
//		}
		

		String s = "0001100001";
		System.out.println(f(s));
//		String[] strs = solve('0', '1', s.length(), count(s));
//		for (String str: strs) {
//			System.out.println(str + "=>" + f(str));
//		}
	}
	
	private static int[] count(String str) {
		
		int[] c = new int[4];
		char[] cs = str.toCharArray();
		for (int i = 1; i < cs.length; i ++) {
			c[((cs[i-1]-'0')<<1) + (cs[i]-'0')] ++;
		}
		return c;
	}
	
	private static String[] nrotate(String str) {

		int len = str.length();
		String[] array = new String[len];
		array[0] = str;
		for (int i = 1; i < len; i ++) {
			array[i] = rotate(array[i-1]);
		}
		return array;
	}
	
	private static String f(String str) {
		
		String[] array = nrotate(str);
		Arrays.sort(array);
		for (int i = 0; i < array.length; i ++) {
			System.out.println(array[i]);
		}
		System.out.println();
		
		int len = str.length();
		char[] cs = new char[len];
		for (int i = 0; i < len; i ++) {
			cs[i] = array[i].charAt(len-1);
		}
		return new String(cs);
	}
	
	private static String rotate(String str) {
		
		char[] cs = str.toCharArray();
		char[] ncs = new char[cs.length];
		for (int i = 0; i < cs.length-1; i ++) {
			ncs[i] = cs[i+1];
		}
		ncs[ncs.length-1] = cs[0];
		return new String(ncs);
	}
	
	/**
	 * 返回以s开始，e结尾，长度是n，
	 * 并且0-0,0-1,1-0,1-1的数目恰好如count[]定义的字符串
	 * 
	 * @param s
	 * @param e
	 * @param n
	 * @param count
	 * @return
	 */
	private static String[] solve(char s, char e, int n, int[] count) {
		
		if (n < 2) {
			throw new RuntimeException("Never Occurs!");
		} else if (n == 2) {
			if (count[((s-'0')<<1) + (e-'0')] == 1) {
				return new String[] {new String(new char[] {s, e})};
			} else {
				return new String[0];
			}
		} else {
			String[] s1 = new String[0];
			int[] c1 = new int[4];
			for (int i = 0; i < 4; i ++) c1[i] = count[i];
			if (c1[(e-'0')] > 0) {
				c1[(e-'0')]--;
				s1 = solve(s, '0', n-1, c1);
			}
			
			String[] s2 = new String[0];
			int[] c2 = new int[4];
			for (int i = 0; i < 4; i ++) c2[i] = count[i];
			if (c2[2 + (e-'0')] > 0) {
				c2[2 + (e-'0')]--;
				s2 = solve(s, '1', n-1, c2);
			}

			int len = s1.length + s2.length;
			String[] array = new String[len];
			for (int i = 0; i < s1.length; i ++) {
				array[i] = s1[i] + e;
			}
			for (int i = 0; i < s2.length; i ++) {
				array[i+s1.length] = s2[i] + e;
			}
			return array;
		}
	}
}